package com.leetcode.leetcode2;

/**
 * 两数相除
 *
 * @author: luhd
 * @create: 2021-09-19
 */
public class Practice29 {
    public static void main(String[] args) {
        int divide = divide(10, 3);
        System.out.println(divide);
    }

    public static int divide(int dividend, int divisor) {
        //只有这种情况会溢出
        if (dividend == -2147483648 && divisor == -1) return 2147483647;
        int sign = (dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0) ? 1 : -1;
        int ans = div(-Math.abs(dividend), -Math.abs(divisor));
        return ans * sign;
    }

    public static int div(int dividend, int divisor) { //全为负
        if (dividend > divisor) return 0;
        int cnt = 1;
        int ds = divisor;
        while (ds - dividend + ds >= 0) {
            cnt += cnt;
            ds += ds;
        }
        return cnt + div(dividend - ds, divisor);
    }
}
